package bit;

import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

/**
 * 布隆过滤器
 *
 * @author cxx
 * @create 2020-04-29 14:52
 **/
public class BloomFilter {

    private static int nbits = 100000;

    private static char[] bytes = new char[nbits/8+1];

    private static int hash1(Object obj){
        if(obj == null){
            return 0;
        }
        return obj.hashCode () % nbits;
    }

    private static int hash2(Object obj){
        if(obj == null){
            return 0;
        }
        MessageDigest md = null;
        try {
            md = MessageDigest.getInstance ("md5");
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException ("no md5");
        }
        byte[] digest = md.digest (String.valueOf (obj.hashCode ()).getBytes ());
        return new BigInteger (1,digest).toString (16).hashCode () % nbits;
    }

    public static void add(Object o){
        int k = hash1 (o);
        add(k);
        int k2 = hash2 (o);
        add (k2);
    }

    private static void add(int k){
        int byteIndex =  k / 8;
        int bitIndex = k % 8;
        bytes[byteIndex] |= (1 << bitIndex);
    }

    public static boolean isExist(Object o){
       int k =  hash1 (o);
       int k2 =  hash2 (o);
        return isExist(k) && isExist(k2);
    }

    private static boolean isExist(int k){
        int byteIndex = k / 8;
        int bitIndex = k % 8;
        return (bytes[byteIndex] & (1 << bitIndex)) != 0;
    }

    public static void main(String[] args) {

        BloomFilter.add ("111");
        BloomFilter.add ("222");
        BloomFilter.add ("333");
        System.out.println (BloomFilter.isExist ("111"));
        System.out.println (BloomFilter.isExist ("222"));
        System.out.println (BloomFilter.isExist ("333"));
        System.out.println (BloomFilter.isExist ("666"));

    }

}
